# fec431d60b2921397fbda6d70ead6aba

def bubble_sort(arr):
    """
    冒泡排序算法
    参数: arr - 需要排序的列表   
    返回: 排序后的列表
    """
    n = len(arr)
    # 创建列表的副本，避免修改原列表
    arr_copy = arr.copy()
    
    # 外层循环控制排序轮数
    for i in range(n):
        # 内层循环进行相邻元素比较和交换
        # 每轮排序后，最大的元素会"冒泡"到末尾，所以可以减少比较次数
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素，则交换它们
            if arr_copy[j] > arr_copy[j + 1]:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
    
    return arr_copy


def bubble_sort_optimized(arr):
    """
    优化版冒泡排序算法
    如果某一轮没有发生交换，说明已经排序完成，可以提前退出
    """
    n = len(arr)
    arr_copy = arr.copy()
    
    for i in range(n):
        # 标记本轮是否发生交换
        swapped = False
        
        for j in range(0, n - i - 1):
            if arr_copy[j] > arr_copy[j + 1]:
                arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
                swapped = True
        
        # 如果没有发生交换，说明已经排序完成
        if not swapped:
            break
    
    return arr_copy


def main():
    """主函数，演示冒泡排序的使用"""
    print("冒泡排序算法演示")
    print("=" * 30)
    
    # 测试用例
    test_cases = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 4, 6, 1, 3],
        [1],
        [],
        [3, 3, 3, 3],
        [9, 8, 7, 6, 5, 4, 3, 2, 1]
    ]
    
    for i, test_case in enumerate(test_cases, 1):
        print(f"\n测试用例 {i}:")
        print(f"原始数组: {test_case}")
        
        # 使用标准冒泡排序
        sorted_arr = bubble_sort(test_case)
        print(f"排序结果: {sorted_arr}")
        
        # 使用优化版冒泡排序
        optimized_sorted = bubble_sort_optimized(test_case)
        print(f"优化版结果: {optimized_sorted}")
        
        # 验证结果是否正确
        expected = sorted(test_case)
        print(f"Python内置排序: {expected}")
        print(f"排序正确: {sorted_arr == expected}")

    print("=" * 30)
    print("冒泡排序算法演示结束")
    print("=" * 30)


if __name__ == "__main__":
    main() 
    
    